{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第十二讲：图和网络\n",
    "\n",
    "## 图和网络"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEACAYAAABVtcpZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtAU3X/B/D3AMcUUC4+yEWTS1OURJbhLTUUEh8J0FS8\nlOGTqKEZmSmKIuAFFXtSSqVS05GP90wxyCkWlnfsGeIlEC8zBLyBIA7GYDu/P3zkl4nKxrazcT6v\nv2zb+Z6PCXufcz7nfL88hmEYEEII4SQztgsghBDCHgoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoB\nQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjh\nMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoB\nQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjhMAoBQgjh\nMAoBQgjhMAu2CyDEWJWUlCAvLw9VVVVQKpXg8/mwsbFBz5494ezszHZ5hOgEhQAh/1NWVoYtW7ZA\nIpFAKpVCqVTC1dUVAoEAZmZmUKvVUCgUKC4uBp/Ph0gkQlBQECZNmgQHBwe2yydEKzyGYRi2iyCE\nTWfOnEFKSgrS09Ph5eUFDw8PuLi4oF27duDxeE99nmEYVFZWoqSkBNeuXUN+fj5CQ0MRHR2N3r17\ns/A3IER7FAKEs8rLyzF9+nQcOXIEIpEIvr6+sLKy0ngcuVyO3NxcSKVSBAQEYP369bC3t9dDxYTo\nHoUA4aT09HRERkZCKBTC398ffD6/2WMqlUpkZ2ejsLAQmzZtQkhIiA4qJUS/KAQIpzAMg5iYGIjF\nYgwfPhxubm4634dMJkNmZiYiIiKwcuXKRi8pEWIsKAQIZzAMg6ioKEgkEoSHh6NNmzZ625dcLseu\nXbswbNgwpKamUhAQo0XPCRDOmDt3LiQSCcaNG6fXAAAAKysrjB8/HgcPHkRMTIxe90VIc1AIEE5I\nT09HWloawsPDIRAIDLJPgUCA8PBwiMViHDhwwCD7JERTdDmItHjl5eXw8vJCcHCwXnoALyKTyZCR\nkYH8/Hy6a4gYHToTIC3e9OnTIRQKWQkAAHBzc4NQKMSMGTNY2T8hz0MhQFq0M2fO4MiRI/D392e1\nDn9/f2RlZSEnJ4fVOgj5OwoB0qKlpKRAJBLp5DmA5ng8zURKSgqrdRDyd9QTIC1WWVkZ3NzcEBUV\npdWTwH/Vo0cPjBw5EsCjJnNubq7GY8jlcqSmpkImk9FcQ8Ro0JkAabG2bNkCLy+vZgdA27Zt8c9/\n/hO1tbVozjGTlZUVunbtCrFY3Kx6CNElCgHSYkkkEnh4eDR7nLCwMFRXV+P3339v9lienp6QSCTN\nHocQXaEQIC2WVCqFi4tLs8bo06cP3NzcsH//ftTV1TW7JmdnZ0il0maPQ4iuUAiQFqmkpARKpRLt\n2rXTeoz27dsjICAAp06dQlFRkU7qsrW1hUKhQGlpqU7GI6S5KARIi5SXlwdXV1et5+zh8XgYOXIk\nKioq8PPPP+usLh6PB1dXV+Tl5elsTEKag0KAtEhVVVXNmh7ijTfeQIcOHbBv3z6oVCodVvZoOomq\nqiqdjkmItigESIukVCphZqbdj7erqysGDBiAkydPoqSkRMeVAebm5qitrdX5uIRog0KAtEh8Ph9q\ntVrj7Xg8HkaMGIGysjL88ssveqgMUKlUsLS01MvYhGiKFponLZKNjQ0UCoXG2/H5fDg4OIBhGCxc\nuPCp9xmGQWhoKEJDQ3Hq1CkcOnRI430oFArY2NhovB0h+kAhQFokHx8fFBcXg2EYjZrD9fX1+O9/\n/9voe87OznBycsKNGzdQVlaGmzdvalwXwzAoLi6Gj4+PxtsSog8UAqRFcnFxAZ/PR2VlJWxtbZu8\nnUqlwo8//tjoe2+88QacnJxw7tw5raaNAICKigoIBAI4OztrtT0hukY9AdJiiUQinTd2m7tMZGlp\nKUQikY6qIaT5KARIizV06FAUFhbqdMzmzrd49epVBAUF6agaQpqPZhElLQ7DMMjIyEBcXBwuXLiA\nWbNmNXsSOV2Qy+VYv349bty4QbOIEqNBZwKkxWAYBunp6fDz80NISEjDdftnNXoN7ffff0ddXR0S\nExNp2ghiNCgEiMljGAb79u1Dr169EBYW9sRsn/X19Thx4gSUSiWLFT56eO3kyZNQKpX48ssv4enp\niTlz5uDu3bus1kUIhQAxWWq1Gnv37oVIJMLIkSOfOTvnP/7xD709+NVUEonkiVlIa2pq8Nlnn8HD\nwwMLFy7E/fv3WayOcBmFADE5arUae/bsga+vL0aNGoVz5841+rlRo0YhNzcXUqkUV65cgUwmM2yh\n/yOTyXDlyhU4OTk99d7Dhw+xbNkyuLu7Y8mSJXjw4AELFRIuoxAgJkOtVmPXrl3o2bMnxowZg/Pn\nzz/1GR6PhzFjxiAvLw979uxBz549YW9vj40bNyIzMxPV1dUGrVkulyMzMxPfffcdrly5grVr1zb6\njEBlZSUWLVoEd3d3JCcnQy6XG7ROwl10dxAxGf/617+wZcuWRt/j8XgIDw9HXFwcvL29G/3M3Llz\nsWvXLowfP75ZM4w2lUKhwPbt2xEeHo7k5OSG12tqavDVV19h+fLlz+wJODo6IjY2FtOmTTNIrYS7\n6EyAmIz+/fs/9RqPx8P48eNx4cIF7Nix45kBAAArV67EsGHDsH37dr0facvlcmzfvh3Dhg3DypUr\nn3ivdevWmDVrFq5du4bly5fDzs7uqe3v3LmDjz/+GHFxcXqtkxAKAWL08vLyMHr0aCxcuBCdO3cG\nAJiZmeGdd97BpUuXsG3bNnTv3v2F4/B4PKSmpiI8PBxisVhvPQKZTAaxWIzw8HCkpqY+8ylja2tr\nzJs3D9evX0dCQgLatm37VL19+/bVS42EPEaXg4jRys3NxeLFi3Hy5El8+umn+OCDD3Dy5EmkpaVh\nwYIF6Nq1q9Zjp6enIzIyEkKhEP7+/uDz+c2uV6lUIjs7G4WFhdi0aRNCQkI02r68vByfffYZvvji\nC8jlcgQEBODq1avo2rUrFi9ejN69eze7RkL+jkKAGB2pVIrExEScOXMGc+bMwbRp09CmTRud76e8\nvBzTp0/HkSNHIBKJ4Ovrq9WTxXK5vOEupMDAQKxbtw729vZa13Xnzh2sWrUKn3zyCRwcHPDtt99i\n2bJlEIlEWLx4MXx9fbUem5C/oxAgRuP3339HYmIifv/9d8ydOxdTp05F69at9b7fnJwcpKSkYP/+\n/ejatSs8PT3h7OwMW1vbRi/lMAyDiooKlJaW4urVqygoKEBYWBiio6Ph5+enlxoVCgW+/vprrFix\nAgMGDEBiYmKTLoER8iIUAoR1OTk5SExMRG5uLmJiYhAZGWmQL/+/Kysrg1gshkQigVQqhUKhgKur\nKwQCAczNzaFSqaBQKFBcXAyBQACRSISgoCBEREQYbC6gx/MPrVq1CkOHDkV8fDyEQqFB9k1aJgoB\nwprTp08jMTER58+fx7x58zB58mSjuh2ytLQUeXl5qKqqQm1tLSwtLWFjYwMfHx/W1wN48OABvvji\nC6xZswZhYWGIi4uDm5sbqzUR00QhQAzu5MmTSExMxKVLlzB//ny8//77tOaulu7fv4/PP/8c69ev\nx9ixY7FgwQK4urqyXRYxIXSLKDGY48ePY+jQoRg3bhxGjhyJwsJCREVFUQA0g52dHZYsWYKCggJY\nW1ujR48emDVrFm7fvs12acREUAiQJnl8wvjDDz9g8uTJOHHixBOvP89vv/2GwMBAvPvuuxgzZgwK\nCwsxbdo0+vLXofbt2yM5ORmXLl2CWq1G9+7dMW/ePJSVlWk13pUrV5CRkaHjKokxohAgTcLj8XD5\n8mWMGjUKmzdvxsmTJxtef5Y///wTQ4YMQUREBMaPH4/Lly9jypQpOrknnzTOyckJKSkpyM3NRUVF\nBbp27YpFixahoqKiyWOo1Wps2LABISEhaN++PWJjY1FVVaXHqgmbKARIk1VVVaF3796ws7NDRkYG\nrl+/DuDZZwN2dnaIiIhAQUEBJk+ejFatWhmyXE7r1KkTvvrqK+Tk5KCoqAhCoRDLli1r0pf5rVu3\nsHv3bkyYMAGLFi3CgQMH4ODggNDQUNZmYiX6QyFAmkwikaBLly5Ys2YNsrOzcerUKQDPPhuwtrZG\nREQEffmzyN3dHZs3b8axY8dw8eJF9OnTB/X19c/dZt++fbh16xZmzJiBGTNm4LfffsP333+P8vJy\nnD592kCVE0Ohu4PICzEMAx6P13BHz86dO9G2bVu89dZbWLt2bbOejiWGdefOHbRr1+6Z/Zjy8nKE\nhYXh5s2bOHv27BPPP9TV1VGgt0B0JkBe6PGR/uHDh+Hj4wMAiIiIwE8//YSzZ8+yWRrRkKOj43Mb\n8jdu3ICdnR3atWsHd3d3fPTRR7h37x4AUAC0UBQC5IUYhkF1dTUsLCwapj2eM2cOKisrG+4S0vYu\nFGJcRCIR1q9fj4yMDKxevRqZmZn4+OOP2S6L6BFdDiJNUllZiY4dO+L48eMNZwNvvvkmLly4gKqq\nqoZ5+ulo0XSp1WqYmf3/caFKpUJKSgo+/fRT7N27FyNGjGCxOqIvdCZAmiQvLw/e3t7o0KEDCgoK\nEB0djWPHjuHOnTt49dVXsWDBAgoAE/c4AB4fF5qbm+ODDz6AQCBouBOMtDwUAqRJ7ty5gzNnzmDk\nyJHo1q0bfv31V6SmpsLNzQ2WlpYNDUQ6sTRNu3fvbrj2z+PxoFKpAACnTp1Cq1ataM3jFsyC7QKI\ncWEYBiqVChYWT/5ovPLKK+jVqxc6duyIzMxMvPrqq3B0dMTDhw/x0Ucf4dixY5gwYcJzHx4jxunh\nw4dYu3YtcnJyMG3aNLi7u8Pc3BwAsG7dOtjY2NAKZy0Y9QQIgEfXg/ft24fFixdj586dT63apVKp\nUFpainbt2sHGxuaJ7ebMmYOYmBg4OjoaumyiA3V1ddiwYQOSkpJgbW2NCRMmAHh0FnDw4EF89NFH\nWLNmDctVEn2hEOA4tVqNvXv3YvHixWjVqhXi4+MREhLSpCP6vzcSiWmrra1FcnIytm/fDh6Ph9at\nW2PixImYPHkyrK2tn/isSqVCRUWFwdZRIPpDIcBRarUae/bswZIlSyAQCBAfH4/g4GC6nEMAPHpe\noHPnzs98v66uDmFhYTA3N8fixYshEokMWB3RJQoBjlGpVNi9ezeWLFkCa2trxMfH45///Cd9+RON\nKRQKbNiwAcuXL0f//v2RmJgIb29vtssiGqIQ4AiVSoWdO3diyZIlsLW1RXx8PIKCgujLnzRbdXV1\nw5KXgYGBiI+PR5cuXdguizQRhUAzlZSUNCxBqFQqwefzYWNjg549e7K+BCEA1NfXY8eOHVi6dCkc\nHBwQHx+PN998k778ic5VVVU1LHkZEhKCuLg4uLu7s10WeQEKAQ2VlZVhy5YtDYuRK5XKhsXIzczM\noFarGxYj5/P5DYuRT5o0yaBNtPr6emzbtg1Lly5Fhw4dEB8fj4CAAPryJ3pXUVGBzz//HOvWrUN4\neDgWLFiAjh07sl0WeQYKgSY6c+YMUlJSkJ6eDi8vL3h4eMDFxQXt2rVr9IuVYRhUVlaipKQE165d\nQ35+PkJDQxEdHY3evXvrrc76+nps3boVy5Ytg4uLC+Lj4zF48GD68icGV1ZWhlWrVmHDhg2YOHEi\n5s2bBycnJ7bLIn9DIfAC5eXlmD59Oo4cOQKRSARfX19YWVlpPI5cLkdubi6kUikCAgKwfv16nU7B\nXFdXh++++w7Lli3DSy+9hPj4ePj7++tsfEK0dfv2baxYsQJpaWmYPHky5s6di/bt27NdFvkfCoHn\nSE9PR2RkJIRCIfz9/XWyLKJSqUR2djYKCwuxadMmhISENHu8tLQ0JCUlwd3dHfHx8Rg0aFCz6yRE\n127evImkpCTs3LkT06dPx+zZs2Fra8tqTcbe0zMECoFGMAyDmJgYiMViDB8+HG5ubjrfh0wmQ2Zm\nJiIiIrBy5UqNL9colUps2bIFSUlJEAqFiI+Px4ABA3ReJyG6JpPJsGTJEqSnpyM6OhrR0dFPPIWu\nT6bS0zMkCoG/YRgGUVFRkEgkCA8PR5s2bfS2L7lcjl27dmHYsGFITU1tUhDU1tZi8+bNWL58Oby8\nvBAfH4/+/fvrrUZC9KWwsBCJiYk4fPgwPv30U8yYMUNvv2+m0tNjA4XA38yZMwd79uzBuHHjIBAI\n9L4/hUKB7du3Izw8HMnJyc/8XG1tLTZt2oQVK1bA29sbixYtQr9+/fReHyH6dvHiRSQkJOD48eOY\nN28epk6dqrPfPVPp6bGJJn75i/T0dKSlpSE8PNwgAQAAAoEA4eHhEIvFOHDgwFPvKxQKrF27Fi+/\n/DIyMjKwe/du/PTTTxQApMXw9vbG7t27kZmZiaysLAiFQnz99ddQKpXNGvfxUX9RURGmTp2K119/\nXasAAAArKyu8/vrrmDp1KoqKiuDl5dXo76spojOB/ykvL4eXlxeCg4P10gN4EZlMhoyMDOTn58Pe\n3h41NTXYsGEDVq5ciVdffRWLFi2Cn5+fwesixNDOnDmDuLg4XL58GYsWLcLEiROfmtr8eUyhp2dM\nKAT+Z9y4cSgqKsLQoUNZq+HQoUNwdXVF//79kZycDD8/PyxatAi9evVirSZC2HLs2DEsXLgQJSUl\nSEhIwNixYxvWOXgWY+/pGSMKATw68ggODsbUqVN1chuotpRKJdasWQM/Pz+sXr2aZmYknMcwDH7+\n+WfExcXhwYMHSExMxMiRI585hbmx9vSMGYUAgHfeeQd3797F66+/rtF23bp1Q+fOneHk5IQOHTrA\n0tISeXl52Ldvn9a1HDt2DB06dMDWrVu1HoOQloZhGPz000+Ii4uDWq3GkiVLnpr6PD09HVOmTMGk\nSZP0egbwd3K5HGKxGBs3bmz2cz9s4HxjuKysDOnp6fD19dV424EDB8LPzw8dOnTAgwcPdLK+rkgk\nwv79+1FWVtbssQhpKXg8HoYPH46zZ88iPj4e8+fPR79+/XD48GEwDIPy8nJERkZi+PDhBg0A4FHT\nePjw4Zg8eTLKy8sNum9d4Pwaw1u2bIGXl5dWdw1IJBI8ePAA9+/fR+fOnREREdHseqysrNC1a1eI\nxWJ88sknzR6PkJaEx+NhxIgRCA0Nxe7duzFz5kw4OjqCz+dDKBSyclMHALi5uUEoFGLGjBnYvn07\nKzVoi/NnAhKJBB4eHlpte+PGDdy/f1/HFQGenp6QSCQ6H5do5vz58xg9ejQ6d+4Ma2trdOrUCW+/\n/Tby8vLYLo3zzMzMMHbsWFy4cAGDBw/GqVOnWJ8ry9/fH1lZWcjJyWG1Dk1x/kxAKpXi3XffZbuM\nJzg7O+OXX35huwzOKysrg5ubG9566y24uLjg3r17WL16Nfr164cTJ06gZ8+ebJfIeRYWFrhy5Qr6\n9++v8U0dgYGBcHZ2hoODA9q0aYO6ujpUVlYiPz8fZ86cgUKh0Gi8x9NMpKSkmFRPj9MhUFJSAqVS\niXbt2rFdyhNsbW2hUChQWlrKmUmsjJG/v/9TR5eDBg2Cl5cXdu7cCW9vb43uXye697inFxUVpfG2\nffr0QWlpKa5evQq5XA4+nw9XV1f4+/vj1VdfxaZNm1BVVaXRmL6+vkhNTUVZWZnJzDXE6Z/gvLw8\nuLq6Gt39vTweD66ursjLy6MQMDIdO3ZEq1atUFdXx3YpBM3r6S1fvhxqtfqp1wcPHoyBAwdiwIAB\n+OmnnzQa0xR7epzuCVRVVRlseghNWVpaQiaT4datW7h37x4qKipQVVWFmpoa1NXVNfrDS/SrvLwc\nM2fORE1NjcZPsRL9aE5P71m/QxcvXgQArecGMrWeHqd/ipVK5TMfOmGbQqHAvHnzsGjRIqhUKtTX\n16O+vv6JP/N4PFhYWMDCwgLm5uYv/LOuP6fPsbWtQR//nkOHDm3o0Tg7O+Po0aPw8fHR+X6Myf37\n93H8+HGd/1vq+t9HHz29rl27Ani0GI42TK2nx+kQ4PP5RntE3bp1a2zYsAGjR49u9H2GYaBWq58Z\nEH/98/Pea+42j/9boVCwXsPjSzSafCmNGTMGMTExz723PCUlBffu3cOff/6JNWvWYPz48cjKymr0\nCFShUGDfvn34448/jCZozczMNL7k+ccff+jlwScej6ezv2t9fT0ePnzY7J5ev379wOfzYWlpCRcX\nF7z00ku4desWjh8/rtV4ptbT43QI2NjYaHwHgKEoFIrnLrTx+JfJ3Nyc1akujI2mwdi2bVtYWlo+\nd8xu3bo1/DkkJAQeHh5YuXIl1q9f3+hcNo+/eJVKpU5DTttt1Gp1wxdnU790a2pqdP5vAzw6eHlc\nny44Ozs3u6fXr1+/J3oKhYWF2L9/v9b/D0ytp8fpEPDx8UFxcTEYhjGq5jDDMCguLm7xlxz0wczM\nDGZmZmjVqpVexm/bti26deuGS5cuNXy5/pVAIMDo0aOfeQbHBoZhNA6YkydPYtq0aWyX/kK6eDr4\n888/bxirU6dOCAwMxLRp07Bt2zatLwkJBAKN7yxiC6dDwMXFBXw+H5WVlVqtddq1a9eG64fW1tYA\ngE6dOiE0NBQAUFNTg8OHD2s8bkVFBQQCgUkcRXCNQqFAQUEBAgMDXzijpbH4a++oqVQqFYKDg3V6\n1qKro/+/0uW/QXV1NQoKClBaWoqZM2di5MiR+Oqrr7Suq7a2Vme16ROnQwB4NFdPSUmJViHg5OT0\nxANDDMPA1ta2YayKigqtQqC0tJRmEDUC48ePh7e3N3r16gU7OztcvXoVq1evRkVFBebMmWO0NxXo\ngq+vL3788Uedj6tWq3XWI8rOztbLwi4PHjzA3bt30aFDBwgEAq0uGatUqhdeZjQWnA+BoKAg7Nix\nA927d9d426NHj+Lo0aM6r+nq1auYMGGCzsclmnnttdewfft2fPbZZw0Lkvft2xdbtmzBK6+8wnZ5\nJsnMzAx8Pl8nfSyVSoUffvhBB1U97XE/TttJIV/U0zMmLfdQpokmTZqE/Px8yOVytksB8Gha2oKC\nAp1MRkeaZ/bs2cjJyWl4TuPChQvYvHkzBYCR+GtPT1P29vbPDKIhQ4bAysoKRUVFWl3SMbWeHufP\nBBwcHBAaGorc3FyN1xPQB6lUiuDgYJN55Lyle3w9nRif5vT0hEIhAgIC8Oeff6KiogLV1dWwtrZG\n586dYWdnh6qqKq0vNZlaT49+ugFER0cjODgYfn5+rK8sdvr0afD5fKxbtw5Tpkyh2z8JeQ5te3rX\nrl2DnZ0dXnrpJTg5OUEgEECpVKKsrAznzp3D6dOntW7smlpPj1YW+x9jWWP4pZdewpw5c7BgwQLk\n5+cjMTER77zzjsnciUKIIf373//Gjh078NZbb7FdSoMDBw5gwoQJJjN3EIXA/5SXl8PLywvBwcGs\nLEwhk8mQkZGBgoIC2NnZAQB+/fVXxMbGoqKiAkuXLkVYWJhRPc9ACNseT/cdFRWl1SRyuiaXy5Ga\nmgqZTGYyl3Q53xh+zN7eHhs3bkRmZiaqq6sNum+5XI7MzExs2rSpIQCAR9MW//bbb0hOTkZCQgL6\n9u2LI0eOGLQ2QozZX3t6xiA3NxdhYWEmEwAAhcATQkNDERERgZ07dxpsOgmFQoFdu3YhIiKi0bla\nHq+t+t///hezZs3CBx98gMDAQJw+fdog9RFi7KKjoyGVSqFUKlmtQ6lUQiqVIjo6mtU6NEWXg/6G\nYRhERUXh4MGDCA8P1+spplwux65duzBs2DCkpqY26VJPXV0dtmzZgsWLF+O1117D0qVL4e3trbca\nCTEFxtTTozWGTRyPx0NqairCw8MhFoshk8n0sh+ZTAaxWIzw8PAmBwAAtGrVClOmTMHly5cxcOBA\nDBkyBO+99x6uX7+ulzoJMQXJycmQSqV6+319EZlMhsLCQqxfv56V/TcHhUAjeDwekpOTsWHDBmRk\nZODQoUM6O9VUKpU4dOgQMjIysHHjRiQnJ2vV7G3dujU++eQTFBYWwsPDA35+fvjwww9RWlqqkzoJ\nMRWVlZWYMGECampqsHv3bqPp6ZkKCoHnCA0NRX5+Pjp16oRvvvkGx48f1/rJYrlcjuPHj+Obb77B\nSy+9hPz8fJ3M1962bVskJCQgPz8flpaWeOWVVzB//nzcv3+/2WMTYuzKy8sRGBjYMPd/TU0Nvv32\nW6Pp6ZkC6gk0UU5ODlJSUrB//3507doVnp6ecHZ2hq2tbaNH8gzDoKKiomEh64KCAoSFhSE6Ohp+\nfn56q7OoqAhLlizBDz/8gFmzZiE6Otoobp0jRNfu3LmDwMBAnD9//onXO3ToAEtLS4wdO9boenrG\niEJAQ2VlZRCLxZBIJJBKpVAoFHB1dYVAIIC5uXnDKlvFxcUQCAQQiUQICgpCRESEQW8bu3z5MuLj\n45GdnY3Y2FhMnTrVZGY1JORFiouLERAQgIKCgide79u3LzIzM7F8+XKIxWIMHz5cL8/9yGQyZGZm\nIiIiAitXrjTZAAAoBJqttLQUeXl5qKqqQm1tLSwtLWFjYwMfHx+jmDskNzcXCxYswKVLl5CQkIB3\n332Xnj4mJk0mkyEgIADXrl174nV/f3+kp6c3zN6Znp6OyMhICIVC+Pv762QKFqVSiezsbBQWFmLT\npk0mewnorygEOOLYsWOIjY3FvXv3sHTpUowcOdKkj14IN12/fh1vvPEGioqKnng9KCgIe/fufWql\nsfLyckyfPh1HjhyBSCSCr6+vVpeI5HI5cnNzIZVKERgYiHXr1sHe3r5ZfxdjQSHAIQzD4ODBg4iN\njYWFhQWSkpIQGBhIYUBMxsOHDzF48GCcPXu24bWwsDDs3LnzuZc7TaWnxwYKAQ5Sq9XYs2cP4uLi\n4OLiguXLl6Nv375sl0XICxUXF2Pw4MF4+PAhSktLMXbsWHz33XdNXlPaVHp6hkQhwGH19fUQi8VI\nTEyESCTCOmHwAAARw0lEQVTC0qVL0aNHD7bLIqRRj3sBU6ZMwZQpU/Dll18iLi6uWT0uY+/pGQKF\nAIFCoUBqaipWrFiBN998E4mJifD09GS7LEIaFBYWIjAwELNnz8ZHH33EdjktCj0sRiAQCDBr1ixc\nuXIFXbp0QZ8+fRAVFYWSkhK2SyMEFy9ehL+/PxYuXEgBoAcUAqSBjY0NFi1ahPz8fFhbW6NHjx6I\niYlBeXk526URjpJKpQgICMDKlSsxZcoUtstpkSgEyFPat2+PVatWIS8vDxUVFejSpQuWLl2Khw8f\nsl0a4ZBTp05h2LBhWLduHd599122y2mxKATIM7m6uuLrr7/GqVOncOnSJbz88stISUnReu1VQprq\n6NGjCAkJwbfffotRo0axXU6LRiFAXujll1/Gtm3bIJFIkJWVhS5duuDbb79FfX0926WRFujQoUMY\nPXo0duzYgeDgYLbLafHo7iCisePHjyM2NhZ37tzBkiVLMGrUKHrgjOjE46ke9u7diwEDBrBdDidQ\nCBCtMAyDQ4cOITY2FjweD8uWLcPQoUMpDIjWdu3ahZkzZ+LHH39scU/lGjMKAdIsarUae/fuxcKF\nC+Hk5ISkpCT0799f43Hq6upw9+5duLi46KFKYuzEYjHmzZuHgwcPomfPnmyXwynUEyDNYmZmhtGj\nR+PChQt47733MH78eISEhCAvL6/JYzAMg61bt2LEiBF4++23sX79eqhUKj1WTYzJV199hYULF+Ln\nn3+mAGABhQDRCQsLC7z//vu4fPkyAgMDMXToUEyYMAFXrlx54bY8Hg/29vawsbHB7du38eGHH2LQ\noEHUeOaA8+fPY8WKFcjOzka3bt3YLoeT6HIQ0YuqqiqkpKSgqKgIKSkpEAgETdouLS0NkZGR+Pe/\n/42ZM2fquUqibwzDPLdPVF1dDYVC0WKmZTZFFAJEr1Qq1Qsn+FKr1TAzM0NFRQXmz5+PPXv24PLl\nyya5aDfXFRUVQSaT4f79+xg4cCD9G5oAuhxE9KopMzyamT36Mbx48SJ2796N999/n748TFBaWhre\nfPNNTJw4ESNGjECfPn1w4MAB6u8YOQoBYhSqq6uRkZEBuVyOqKgotsshGvrss88wc+ZMTJo0CZs3\nb8ahQ4fQtm1bzJs3D3fu3GG7PPIcFmwXQAjwaKrgHTt2YMyYMXpZGJzoT3Z2Nv7zn/8gISEBUVFR\nDf2ftWvXYtCgQZBIJJg0aRK7RZJnohAgrKutrUVWVhZkMhl2797NdjlEQ4+nHA8LC3viBgAnJyfY\n2Ng0nAm8qElM2EEhQFhTX18PCwsLlJSUYNu2bQgMDESvXr3YLotoaNy4cejRowc8PDwaXmMYBm5u\nbrC0tERVVRUAUAAYKQoBwooLFy7g8OHDGD58OH777TdIpVJIJBIAdMRoaszMzJ5alpTH4zWs10tP\ngRs3CgHCiqysLMyePRurV6+GWq1G9+7d0adPHwB0xNgSqFQqlJeXo66uDu3bt294vaqqCrm5uejd\nuzcsLS1ZrJA8RncHEVZ8/PHHqKysxKRJk1BXV4c//vgDsbGxOHHiBJRK5VOfr6mpQWlpKQuVEm2Y\nm5tDoVCgtrYWfD4fAPDnn39i5MiRmD9/Ph48eMByheQxCgHCGhsbGyxevBi3b9/Gl19+iR9//BHz\n5s1rdLoIlUqFnj17YurUqbh58yYL1RJNPXz4ECqVCnZ2dsjLy8OwYcNQVFSEPXv24B//+Afb5ZH/\noRAgRmH69OmQyWTYvHkz2rRp89T71tbWyM/Ph729PXx8fDB79mzcvXuXhUpJU92+fRsODg745Zdf\nMHjwYHh6eqKgoABOTk5sl0b+gkKAGBVPT89nvmdvb48VK1bg4sWLUCgU8PLyQkJCAl1aMFJ1dXW4\nd+8eEhMTMW3aNBw4cIDtkkgjKASIyXF2dsa6deuQk5ODa9euQSgU4vPPP0dNTQ3bpXFSTU1No+tO\n9+3bFx07dsT+/fuRlJTEQmWkKSgEiMny8PBAWloajhw5gl9//RVdunTBhg0bUFdXx3ZpnPHHH3/g\ntddea/T/uY2NDa5cuYKQkBAWKiNNRSFATN4rr7yCffv2Yc+ePdixYwe8vb2xY8cOqNVqtktr0c6d\nO4chQ4YgJiYG1tbWjX7m8Z1BxHjRVNKkxcnKykJsbCyUSiWWLVuG4cOH07MHOnbmzBmEhIRg7dq1\nGDNmDNvlkGagECAtEsMw2LdvHxYuXAh7e3skJSVh4MCBbJfVIhw7dgxvv/02Nm3aRJd6WgAKAdKi\nqVQq/Oc//0F8fDy8vLyQlJQEkUjEdlkmKysrC+PHj8e2bdvw5ptvsl0O0QHqCZAWzdzcHO+99x7y\n8/MRHByM4cOHIzw8HAUFBWyXZnIyMjIwfvx4fP/99xQALQiFAOEES0tLfPjhh7hy5QpEIhEGDBiA\nyMhIFBUVsV2aSfj+++/x/vvv48cff8SgQYPYLofoEIUA4RQrKyvMnz8fly9fhqOjI3x9fTFr1ix6\n+vg5tm7dig8//BAHDx5smOSPtBwUAoST7OzskJSUhIsXL6K+vh5eXl5YtGgRKisr2S7NqGzYsAEx\nMTHIysqiXkoLRSFAOM3JyQlffvklzp49ixs3bkAoFOKzzz6jp48BfPHFF1i6dCmys7Ph7e3NdjlE\nTygECAHg7u4OsViMX375BSdOnIBQKMTXX3+Nuro65ObmYsGCBaioqGC7TINZsWIFUlJScPToUQiF\nQrbLIXpEt4gS0ogzZ85gwYIFuH79OqytrXHu3DnY2dkhJiYGM2fObHSm05aAYRjEx8dj9+7dyMrK\ngqurK9slET2jECDkOdasWYNZs2Y98ZqTkxPi4uIQGRnZoqZFYBgGc+bMweHDh3H48GE4OjqyXRIx\nAAoBQp5jxIgR2L9/f6Pvubu7IzExERMmTIC5ubnBaiopKUFeXh6qqqqgVCrB5/NhY2ODnj17wtnZ\nWasx1Wo1PvzwQ+Tk5EAikcDe3l7HVRNjRSFAyHM8fPgQX3zxBZKTk59555C3tzeWLl2KsLAwvcxR\nVFZWhi1btkAikUAqlUKpVMLV1RUCgQBmZmZQq9VQKBQoLi4Gn8+HSCRCUFAQJk2aBAcHhxeOr1Kp\nEBkZicLCQmRkZKBdu3Y6/zsQ40UhQEgTlJeXY9WqVUhJSXnmnUN9+vRBUlIShgwZopN9njlzBikp\nKUhPT4eXlxc8PDzg4uKCdu3aNRo2DMOgsrISJSUluHbtGvLz8xEaGoro6Gj07t270X3U1dVh4sSJ\nuHv3LtLT02FlZaWT2onpoBAgRAOlpaVYunQpvvnmm0bXQgaAwMBALFu27JlfvC9SXl6O6dOn48iR\nIxCJRPD19dXqy1kulyM3NxdSqRQBAQFYv379E5d5amtrMXbsWNTV1WHPnj1o3bq1VvUS00YhQIgW\nrl27hoSEBGzduhXP+hUaOXIklixZotE99unp6YiMjIRQKIS/v79OGs9KpRLZ2dkoLCxsmPmzuroa\nb7/9NqysrLB9+/YW1eAmmqEQIKQZLly4gLi4OOzbt6/R93k8HiZOnIiEhAS4u7s/cxyGYRATEwOx\nWIzhw4fDzc1N57XKZDJkZmZi/PjxyM3NRceOHbFlyxZYWFjofF/EdFAIEKIDp0+fRmxsLH7++edG\n32/VqhWmTp2KhQsXwsnJ6Yn3GIZBVFQUJBIJwsPD9foMglwuR1paGhwcHHDu3DkKAEJPDBOiC336\n9MGRI0eQlZUFPz+/p96vq6vDunXr4OHhgfnz5+P+/fsN782dOxcSiQTjxo3T+0NoVlZW+Ne//gW5\nXI7Y2Fi97ouYBjoTIETH/rqq2aVLlxr9jK2tLebOnQtPT0/MnDkTkyZNMuhTyHK5HGKxGBs3bqTV\nwTiOQoAQPfnrqmYymazRz/D5fEyYMEEvPYAXkclkyMjIQH5+Pj0cxmF0OYgQPXm8qllBQQHWrl2L\nDh06PPG+hYUFevTowUoAAICbmxuEQiFmzJjByv6JcaAQIETP+Hw+ZsyYgatXryIpKQm2trYAHjWL\ng4KCWK3N398fWVlZyMnJYbUOwh66HESIgd2/fx9vvPEGHB0dMXDgwCZvJxAI0K1bNwiFQjg6OqJt\n27ZQqVS4ffs2cnNzkZubq1U9x48fh6OjI7Zu3arV9sS00ZkAIQamVqtx/fp1vPrqqxpt5+3tjZCQ\nELi6uuLmzZs4deoULl26BEdHR4SGhmL06NFa1ePr64v9+/ejrKxMq+2JaTNPSEhIYLsIQrgkNTUV\nt27dwiuvvKLRdnw+H3/88UdDM/f69eu4fPkypFIpvL290bFjR9y5cwf37t3TeNyysjKo1Wr069dP\no22J6aMzAUIMTCKRwMPDQ+Ptbty4gcLCwqder66uxu+//w4ej6d1k9nT0xMSiUSrbYlpoxAgxMCk\nUilcXFx0OqZKpQLw6FKTNpydnSGVSnVZEjERFAKEGFBJSQmUSqVO5+zn8Xjo2bMnGIbBlStXtBrD\n1tYWCoUCpaWlOquLmAYKAUIMKC8vD66urjpdfCYwMBCOjo4oLCzEtWvXtBqDx+PB1dUVeXl5OquL\nmAYKAUIMqKqqCgKBQGfj9e7dG/369cPdu3fxww8/NGssgUCAqqoqHVVGTAVNIUiIASmVSpiZ6ebY\ny8/PD8OGDcOdO3eQlpaG2traZo1nbm7e7DGI6aEQIMSA+Hy+1s3bv+rTpw+CgoJw+/ZtpKWlPXPJ\nS02oVCpYWlo2exxiWigECDEgGxsbKBSKZo3x+uuvIyAgAKWlpfjuu++aPd5jCoUCNjY2OhmLmA4K\nAUIMyMfHB8XFxWAYRqvm8KBBg+Dv74/i4mJs3bpVZ5dvGIZBcXExfHx8dDIeMR0UAoQYkIuLC/h8\nPiorKxsmkmuqnj17wt/fH2q1GkVFRejbt+9Tn6moqMC5c+c0rquiogICgQDOzs4ab0tMG4UAIQYm\nEolQUlKicQjY2to2nEH06dOn0c/cuHFDqxAoLS2FSCTSeDti+igECDGwoKAg7NixA927d9dou6NH\nj+Lo0aN6qenq1auYMGGCXsYmxo2eEyDEwCZNmoT8/HzI5XK2SwHwaKnJgoICREREsF0KYQGFACEG\n5uDggNDQUK3n/9e13NxchIWFwcHBge1SCAsoBAhhQXR0NKRSKZRKJat1KJVKSKVSREdHs1oHYQ+F\nACEs6N27NwICApCdnc1qHdnZ2QgMDISfnx+rdRD20PKShLCkvLwcXl5eCA4OZmWxeZlMhoyMDBQU\nFMDOzs7g+yfGgc4ECGGJvb09Nm7ciMzMTFRXVxt033K5HJmZmdi0aRMFAMdRCBDCotDQUERERGDn\nzp06m/7hRRQKBXbt2oWIiAiEhIQYZJ/EeNHlIEJYxjAMoqKicPDgQYSHh8PKykpv+5LL5di1axeG\nDRuG1NRUna5rQEwTnQkQwjIej4fU1FSEh4dDLBZDJpPpZT8ymQxisRjh4eEUAKQBnQkQYkTS09MR\nGRkJoVAIf39/8Pn8Zo+pVCqRnZ2NwsJCbNq0iS4BkSdQCBBiZMrLyzF9+nQcOXIEIpEIvr6+Wl0i\nksvlyM3NhVQqRWBgINatWwd7e3s9VExMGYUAIUYqJycHKSkp2L9/P7p27QpPT084OzvD1ta20Us5\nDMOgoqICpaWluHr1KgoKChAWFobo6Gh6DoA8E4UAIUaurKwMYrEYEokEUqkUCoUCrq6uEAgEMDc3\nh0qlgkKhQHFxMQQCAUQiEYKCghAREUFTQZAXohAgxMSUlpYiLy8PVVVVqK2thaWlJWxsbODj40Pr\nARCNUQgQQgiH0S2ihBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDC\nYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQC\nhBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDC\nYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYRQChBDCYf8H\nAJZfW2rGn+QAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x104b99e10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "dg = nx.DiGraph()\n",
    "dg.add_edges_from([(1,2), (2,3), (1,3), (1,4), (3,4)])\n",
    "edge_labels = {(1, 2): 1, (1, 3): 3, (1, 4): 4, (2, 3): 2, (3, 4): 5}\n",
    "\n",
    "pos = nx.spring_layout(dg)\n",
    "nx.draw_networkx_edge_labels(dg,pos,edge_labels=edge_labels, font_size=16)\n",
    "nx.draw_networkx_labels(dg, pos, font_size=20, font_color='w')\n",
    "nx.draw(dg, pos, node_size=1500, node_color=\"gray\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "该图由4个节点与5条边组成，\n",
    "\n",
    "$$\n",
    "\\begin{array}{c | c c c c}\n",
    "       & node_1 & node_2 & node_3 & node_4 \\\\\n",
    "\\hline\n",
    "edge_1 & -1     & 1      & 0      & 0      \\\\\n",
    "edge_2 & 0      & -1     & 1      & 0      \\\\\n",
    "edge_3 & -1     & 0      & 1      & 0      \\\\\n",
    "edge_4 & -1     & 0      & 0      & 1      \\\\\n",
    "edge_5 & 0      & 0      & -1     & 1      \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "我们可以建立$5 \\times 4$矩阵\n",
    "$\n",
    "A=\n",
    "\\begin{bmatrix}\n",
    "-1 & 1 & 0 & 0 \\\\\n",
    "0 & -1 & 1 & 0 \\\\\n",
    "-1 & 0 & 1 & 0 \\\\\n",
    "-1 & 0 & 0 & 1 \\\\\n",
    "0 & 0 & -1 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "$\n",
    "\n",
    "观察前三行，易看出这三个行向量线性相关，也就是这三个向量可以形成回路（loop）。\n",
    "\n",
    "现在，解$Ax=0$：\n",
    "$\n",
    "Ax=\n",
    "\\begin{bmatrix}\n",
    "-1 & 1 & 0 & 0 \\\\\n",
    "0 & -1 & 1 & 0 \\\\\n",
    "-1 & 0 & 1 & 0 \\\\\n",
    "-1 & 0 & 0 & 1 \\\\\n",
    "0 & 0 & -1 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "x_1\\\\x_2\\\\x_3\\\\x_4\\\\\n",
    "\\end{bmatrix}\n",
    "$。\n",
    "\n",
    "展开得到：\n",
    "$\\begin{bmatrix}x_2-x_1 \\\\x_3-x_2 \\\\x_3-x_1 \\\\x_4-x_1 \\\\x_4-x_3 \\\\ \\end{bmatrix}=\\begin{bmatrix}0\\\\0\\\\0\\\\0\\\\0\\\\ \\end{bmatrix}$\n",
    "\n",
    "引入矩阵的实际意义：将$x=\\begin{bmatrix}x_1 & x_2 & x_3 & x_4\\end{bmatrix}$设为各节点电势（Potential at the Nodes）。\n",
    "\n",
    "则式子中的诸如$x_2-x_1$的元素，可以看做该边上的电势差（Potential Differences）。\n",
    "\n",
    "容易看出其中一个解$x=\\begin{bmatrix}1\\\\1\\\\1\\\\1\\end{bmatrix}$，即等电势情况，此时电势差为$0$。\n",
    "\n",
    "化简$A$易得$rank(A)=3$，所以其零空间维数应为$n-r=4-3=1$，即$\\begin{bmatrix}1\\\\1\\\\1\\\\1\\end{bmatrix}$就是其零空间的一组基。\n",
    "\n",
    "其零空间的物理意义为，当电位相等时，不存在电势差，图中无电流。\n",
    "\n",
    "当我们把图中节点$4$接地后，节点$4$上的电势为$0$，此时的\n",
    "$\n",
    "A=\n",
    "\\begin{bmatrix}\n",
    "-1 & 1 & 0 \\\\\n",
    "0 & -1 & 1 \\\\\n",
    "-1 & 0 & 1 \\\\\n",
    "-1 & 0 & 0 \\\\\n",
    "0 & 0 & -1 \\\\\n",
    "\\end{bmatrix}\n",
    "$，各列线性无关，$rank(A)=3$。\n",
    "\n",
    "现在看看$A^Ty=0$（这是应用数学里最常用的式子）：\n",
    "\n",
    "$A^Ty=0=\\begin{bmatrix}-1 & 0 & -1 & -1 & 0 \\\\1 & -1 & 0 & 0 & 0 \\\\0 & 1 & 1 & 0 & -1 \\\\0 & 0 & 0 & 1 & 1 \\\\ \\end{bmatrix}\\begin{bmatrix}y_1\\\\y_2\\\\y_3\\\\y_4\\\\y_5\\end{bmatrix}=\\begin{bmatrix}0\\\\0\\\\0\\\\0\\end{bmatrix}$，对于转置矩阵有$dim N(A^T)=m-r=5-3=2$。\n",
    "\n",
    "接着说上文提到的的电势差，矩阵$C$将电势差与电流联系起来，电流与电势差的关系服从欧姆定律：边上的电流值是电势差的倍数，这个倍数就是边的电导（conductance）即电阻（resistance）的倒数。\n",
    "\n",
    "$\n",
    "电势差\n",
    "\\xrightarrow[欧姆定律]{矩阵C}\n",
    "各边上的电流y_1, y_2, y_3, y_4, y_5\n",
    "$，而$A^Ty=0$的另一个名字叫做“基尔霍夫电流定律”（Kirchoff's Law, 简称KCL）。\n",
    "\n",
    "再把图拿下来观察："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEACAYAAABVtcpZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlYU1f+P/B3QGOURhGtCrigFAFlSx2kbi0VKxYK1LZS\nxbYQRVRcaOvCOO24z7R2c+wirRUCSl2otYqFGisFF6yKGsSNRRalARWILAZDILm/P/zKTwpaCElu\nQj6v5+nTmuTe+2FGzjv3nHPP4TAMw4AQQohJMmO7AEIIIeyhECCEEBNGIUAIISaMQoAQQkwYhQAh\nhJgwCgFCCDFhFAKEEGLCKAQIIcSEUQgQQogJoxAghBATRiFACCEmjEKAEEJMGIUAIYSYMAoBQggx\nYRQChBBiwigECCHEhFEIEEKICaMQIIQQE0YhQAghJoxCgBBCTBiFACGEmDAKAUIIMWEUAoQQYsIo\nBAghxIR1Y7sAQghhS1lZGXJyclBXVwelUgkulws+nw93d3dYW1uzXZ5eUAgQQkxGVVUV4uPjIRaL\nIZFIoFQqYWtrCx6PBzMzM6jVaigUCkilUnC5XAgEAvj6+iIsLAz9+vVju3yd4DAMw7BdBCGE6NLZ\ns2exZcsWJCcnw8nJCSNGjICNjQ369OkDDofT6vMMw6CmpgZlZWUoKipCbm4uAgMDERUVhbFjx7Lw\nE+gOhQAhpMuSyWSIjIxEWloaBAIBPDw8YGFh0eHzyOVyZGdnQyKRwMfHB1u3boWVlZUOKtY/CgFC\nSJeUnJyM8PBwODg4wNvbG1wut9PnVCqVyMjIQEFBAWJjYxEQEKCFStlFIUAI6VIYhkF0dDQSEhLg\n5+cHOzs7rV+jpKQEqampCA0NxaZNm9rsUjIWFAKEkC6DYRgsXLgQYrEYwcHB6NWrl86uJZfLkZSU\nhGnTpiEmJsZog4CeEyCEdBkrV66EWCzGzJkzdRoAAGBhYYFZs2bh8OHDiI6O1um1dIlCgBDSJSQn\nJ2PHjh0IDg4Gj8fTyzV5PB6Cg4ORkJCAQ4cO6eWa2kbdQYQQoyeTyeDk5AR/f3+djAH8nZKSEqSk\npCA3N9foZg3RnQAhxOhFRkbCwcGBlQAAADs7Ozg4OGDRokWsXL8zKAQIIUbt7NmzSEtLg7e3N6t1\neHt74+jRo8jKymK1jo6i7iBCiFGbPXs2KioqMGHChA4dN2XKFFhbW6Nfv37o1asXGhsbUVNTg9zc\nXJw9exYKhaLDtWRmZmLAgAFITEzs8LFsoTsBQojRqqqqQnJyMjw8PDp8rJeXF7p3747CwkKcPn0a\nly5dgkqlgre3NxYsWAA+n9/hc3p4eODgwYOoqqrq8LFsMV+7du1atosghBBNxMTE4NatW3Bxcenw\nsZmZmbhw4QLy8/NRXFyM69evQyKRwMzMDCNHjkS3bt1w/fr1Dp2Ty+WiqqoKarUa48aN63BNbKA7\nAUKI0RKLxRgxYoRGx6rV6jZfv3LlCgBoPMvH3t4eYrFYo2PZQCFACDFaEokENjY2Wj2no6MjAOD2\n7dsaHW9tbQ2JRKLNknSK9hMghBilsrIyKJVK9OnTp1PnGTduHLhcLnr06AEbGxsMHToUt27dQmZm\npkbns7S0hEKhQHl5uVFsTEMhQAgxSjk5ObC1te30mj3jxo1rsbx0QUEBDh48iPv372t0Pg6HA1tb\nW+Tk5FAIEEKIrtTV1WlleYgvvvgCANCrVy8MGTIEU6ZMwfz587Fr1y6Nu4R4PB7q6uo6XZs+0JgA\nIcQoKZVKmJlprwmrr69HXl4edu7ciV69emH69Okan8vc3BwNDQ1aq02XKAQIIUaJy+U+doZPZ9TW\n1qKiogJPP/20xncaKpUKPXr00HJlukEhQAgxSnw+X6Onett7buDB/gSaUCgUGj1sxgYKAUKIUXJz\nc4NUKtWoobaysnrsdpOTJ0+GhYUFSktLNerSYRgGUqkUbm5uHT6WDTQwTAgxSjY2NuByuaipqYGl\npWWHjnVwcICPjw9u3ryJ6upq1NfX46mnnsKwYcPQt29f1NXVabw/QHV1NXg8nlHMDAIoBAghRszZ\n2RllZWUdDoGioiL07dsXQ4cOxaBBg8Dj8aBUKlFVVYWLFy/izJkzGg/slpeXQyAQaHQsGygECCFG\n5f79+9i/fz9EIhEuXLgAe3t7jBo1qkPnqKiowOHDh3VSX2FhIUJCQnRybl2gMQFCiMFjGAanT5/G\n/PnzYWtri8TERERERCAvLw9FRUWQy+VslwjgwebzeXl5CA0NZbuUdqM7AUKIwSovL8fOnTsRHx+P\npqYmCIVCXLp0Cba2tgAezMKxs7PDhQsXMGnSJJarBbKzsxEUFIR+/fqxXUq7UQgQQgyKUqnEoUOH\nIBKJkJmZiddffx3ff/89xo8f32KJiNOnT2POnDm4du0aCgsL4eXl9dgZP/qqWyKRIDU1lbUaNEE7\nixFCDEJ2djZEIhF27doFFxcXCIVCvP766y3W9QEejAmsXr0aX3zxRfPDYt26dYO7uzsCAgLYKB0A\ncOTIEQwdOhS7d+9mrQZN0J0AIYQ1VVVV+OGHHyASiSCTyRAWFoYzZ848do+AU6dOQSgUIj8/v8Xr\nTU1NuHTpElxdXVnZbL6kpAQFBQX45Zdf9H7tzqKBYUKIXjU1NSElJQVvvPEG7O3tcfbsWXz22Wco\nLi7GunXr2gyA+vp6vP/++5g4cWKrAACAuXPnIj4+Hqmpqaivr9fHj9FMLpcjNTUVsbGx6Nu3r16v\nrQ10J0AI0Yvc3FyIRCLs3LkTw4YNg1AoRGxs7N/uB3DixAnMmTOnza0ehwwZgu+//x6+vr4AHmwy\ns3fvXsyaNUsrK4z+HYVCgaSkJISGhrLaFdUZNCZACNGZmpoa7N27FyKRCDdu3MDbb7+NsLAwODs7\n/+2xcrkcq1atwtdff93m0hARERH49NNP0bt37+bXGIbBwoULcfjwYQQHB7caT9AmuVyOpKQkTJs2\nDTExMZ3e14AtFAKEEK1Sq9VIT0+HSCTCL7/8gilTpkAoFMLX1xfdurWv8yEjIwNz585FUVFRq/eG\nDRuG2NhY+Pj4tHkswzCIjo5GQkIC/Pz8dDJGUFJSgtTUVISGhmLTpk1GGwAAhQAhREuKi4sRHx+P\nhIQE9O3bF0KhECEhIejfv3+7z3Hv3j1ER0dj69atbb4fGRmJjz/+uF0rdCYnJyM8PBwODg7w9vbW\nyvRRpVKJjIwMFBQUIDY21mi7gB5FIUAI0ZhcLsdPP/0EkUiEy5cvIyQkBEKhEB4eHh0+V1paGubO\nnYsbN260em/48OGIjY3Fiy++2KFzymQyREZGIi0tDQKBAB4eHhp1EcnlcmRnZ0MikWDKlCn45ptv\nYGVl1eHzGCIKAUJIhzAMg1OnTkEkEmH//v0YP348hEIhXnnlFY02UqmtrcWKFSuwbdu2Nt9funQp\n/vvf/3aqfz8rKwv//Oc/cfz4cTg4OMDV1RXW1tawtLRssyuHYRhUV1ejvLwchYWFyMvLQ1BQEKKi\nouDp6alxHYaIZgcRQtpFKpVix44diI+Ph5mZGYRCIa5cudKpJZOPHDmC8PBwlJaWtnrvmWeeQVxc\nnFaWg/D09MSYMWPw+++/Nz9h3L17d5iZmcHW1hY8Hg/m5uZQqVRQKBSQSqXg8XgQCAQICQlBaGio\nUS0F0REUAoSQx2poaMDBgwchEolw5swZzJgxAwkJCfDy8urUYGhNTQ2WLVuG2NjYVu9xOBy8++67\n2LhxI3r16tWZ8lvIyMho/m+lUomdO3di0qRJyMnJQV1dHRoaGtCjRw/w+Xy4ubkZzX4AnUXdQYR0\nMVKpFHFxcfjggw802oidYRhcuHABIpEIe/bsgYeHB4RCIaZPn66VRjk1NRURERGQSqWt3hs5ciRE\nIhHGjx/f6es8qqamBlZWVi32JL516xYGDhyo1esYI3pimJAuYseOHRgzZgzs7Oywc+dOFBcXd+j4\niooKbN68Ge7u7pgxYwYGDBiAc+fO4ejRo5g9e3anA+Du3bsICwuDv79/qwAwMzPDihUrkJ2drfUA\nAICTJ0+2CIBRo0ZRAPwf6g4ixIipVCps2bIFy5cvx8CBAzFjxgx8/fXXcHV1xVNPPfW3xzc2NuLX\nX3+FSCRCeno6goKC8OWXX+L555/X6C7icQ4dOoT58+ejvLy81XvOzs4QiUTw8vLS2vX+Kj09vcWf\nvb29dXYtY0MhQIgR43A4uHXrFjgcDn788UeMGzcO5ubm7Tq2oaEBgYGBkMvlEAqFSEhIaPH0rTZU\nVVUhKioKP/zwQ6v3zMzMEB0djdWrV+t8iYe/hkBHp5p2ZTQmQIiRu3DhAiZOnIgvv/wS4eHhAICC\nggLweDwMGTIEwIN+/r8O5KpUKtTV1XV4f972OnDgABYsWIDbt2+3es/FxQUikQj/+Mc/dHLtR1VX\nV8PKyqrF0hN37tzB008/rfNrGwO6EyDEyI0aNQrjxo1DbGwspFIpRCIR5HI5+Hw+nJ2d8e233zaH\nwaPMzc11EgCVlZVYsmQJ9uzZ0+Y1V61ahQ8//FCjZwo0cfz48RYB4OLiQgHwCAoBQowcj8fDrFmz\nEBERAQ6Hgzlz5sDR0RHnzp3Dd999h5CQEMTExMDFxUXntezbtw+RkZGoqKho9Z6bmxtEIhGeffZZ\nndfxqEenhgI0HtAKQwgxesXFxcy//vUv5syZM4xarW5+PT4+nunbty/zwQcf6PT6t2/fZmbMmMEA\naPVPt27dmLVr1zINDQ06reFxPDw8WtTz008/sVKHoaIxAUK6ALVaDZVKhe7du7d4XaFQQCAQwN7e\nHj/++CN69uyp1esyDIOkpCQsXrwYlZWVrd4XCAQQiURwd3fX6nXbSy6X4+mnn8b9+/ebX6uoqOjQ\nonZdHXUHEdIFmJmZwczMrHku/MPpnTwer3m3qx49erQ5QKypW7duITIyEj///HOr97p3747Vq1cj\nOjq6VTDpk4WFBWQyGTw9PeHh4YHu3btTAPwFhQAhRuL+/fvIysrCmDFj2lxMjWGYVnP7k5OTcebM\nGSxfvlxr8/4ZhsGuXbuwdOlSyGSyVu+PGTMG8fHxehmDaA+VSoXi4mKcPn1ap5vMGCsKAUIMGMMw\nyMrKgkgkQlJSEry8vHDw4ME2P8vhcNDY2IiysjI0NDQgKysLX331FSZPnowPP/xQK/WUl5djwYIF\nSE5ObvUel8vFunXrsHz58nZvHqMPp06d0ngJaVNgOP9PEUKa3b59Gzt37oRIJEJDQwOEQiGys7Pb\nnOr5qOjoaOTk5KCgoACVlZUIDg7Gv/71L/D5/E51BTEMgx07duDdd99FdXV1q/e9vLwQFxeHUaNG\naXR+XUpPT6eHw56ABoYJMRBKpRIpKSkQiUQ4ceIEpk+fDqFQiIkTJ7a78c7Pz8euXbswevRovPHG\nG1rp/5dKpYiIiEBqamqr93r06IGNGzfivffea/eTyvo2fvx4bNiw4bHbUZo6CgFCWJaTkwORSIRd\nu3bByckJQqEQb7zxRrvW/tElhmEgEonw/vvvo6amptX748ePR1xcHBwdHVmorn3u3buHQYMG4c6d\nO1pdlroroe4gQlggk8mwa9cuiEQiVFRUIDQ0FJmZmXjmmWfYLg0AcPPmTUREREAsFrd6r2fPnvjP\nf/6DpUuXGuy3/4cyMzPx7LPPUgA8AYUAMWhlZWXNm34olUpwuVzw+Xy4u7sb3aYfKpUKR44cgUgk\nwpEjR+Dn54ePP/4YkydPNqjGtLi4GO7u7qirq2v13qRJkxAbGwsHBwcWKus4Gg/4exQCxKBUVVUh\nPj4eYrEYEokESqWyefu/h/PgH27/x+VyIRAI4Ovri7CwMIPd/i8/Px8ikQg7duzA4MGDIRQKsW3b\nNp0t3NZZdnZ2cHV1xalTp5pf69WrFz7++GMsWrRIq0tM61pGRgY+/vhjtsswaDQmQAzC2bNnsWXL\nFiQnJ8PJyQkjRoyAjY0N+vTp89iNwGtqalBWVoaioiLk5uYiMDAQUVFRGDt2LAs/QUu1tbVISkqC\nSCRCYWEh3n77bYSFhWH06NFsl/ZEtbW1WL58OVJSUlBbW4t79+7B29sb27dvh729PdvldUhdXR2s\nra1RWVmp86WqjRmFAGGVTCZDZGQk0tLSIBAINJ7PLZfLkZ2dDYlEAh8fH2zduhVWVlY6qPj/a2xs\nbPE0rFqtxrFjxyASiZCcnIzJkydDKBRi2rRprD41215isRgRERHw9fXFp59+isOHD6OqqgoLFiww\nqm//D/3666/45JNPWu0lQFqiECCsSU5ORnh4OBwcHODt7Q0ul9vpcyqVSmRkZKCgoACxsbEICAjQ\nQqX/H8MwOH/+fPP+u1lZWTAzM0NCQgISEhLA5/MhFAoREhKCAQMGaPXaulJdXY1ly5YhLS0N33//\nPV566SW2S9KKlStXwsLCAmvWrGG7FINGIUD0jmEYREdHIyEhAX5+frCzs9P6NUpKSpCamorQ0FBs\n2rSp0/Plb9++jcTERMTHx+Py5cvNr9vZ2aGurg6zZs2CUCiEQCDQ2to8+pCSkoIFCxbglVdewSef\nfAI+n892SVozduxYfPbZZ3j++efZLsWgUQgQvWIYBgsXLoRYLEZwcLBOp+7J5XIkJSVh2rRpiImJ\n6XDj3NjYiNTUVMTFxSE1NRVNTU2tPtO/f3/cvHlT66tz6trdu3fx3nvv4fjx49i+fTsmT57Mdkla\nVVNTg8GDB6OyslJvm9cYK+Pr6CNGbeXKlRCLxZg5c6bO525bWFhg1qxZOHz4MKKjo9t93KVLl7Bs\n2TIMHjwYr776KpKTk9sMgIf+/PNPbZSrN8nJyXBxcQGfz0dOTk6XCwAAOHHiBMaOHUsB0A40RZTo\nTXJyMnbs2IGwsDC9zdbg8XgIDg5GQkICJk2a9NgxAplMht27d0MkEuH8+fNPPKe5uTn8/PwgFArh\n7++vlbEMfXi46fvp06exa9cuvPDCC2yXpDMZGRm0g1g7UQgQvZDJZAgPD4e/v7/en960sLCAn58f\n5s6di9zc3OZZQyqVCkePHkVcXBwOHDgApVL5xPOMGjUKQqEQb731FgYNGqSP0rXm559/xqJFi/Dm\nm2/i4sWLXX5FzfT0dGzZsoXtMowCjQkQvZg5cyZKS0sxdepU1mo4cuQIhg4divXr1zc/vCWVSp94\nTJ8+fZoHfT09PY1q0Bd4sIvWkiVLcOHCBYhEIkyYMIHtknSuuroaQ4YMofGAdqIxAaJzZ8+eRVpa\nGuu3597e3vjll18wcuRIfPTRR48NAA6Hg5deegm7du1CeXk5YmJiMHbsWKMLgB9//BFubm4YPHgw\nsrOzTSIAAOD48eN47rnnKADaibqDiM5t2bIFAoGg033nrq6umD59OoAH4wvZ2dkdOp7L5WLs2LE4\nfvx4mwO99vb2CAsLwzvvvIOhQ4d2qlY23blzB4sWLcLly5exf/9+jBs3ju2S9IrGAzqG7gSITlVV\nVSE5ORkeHh6dOk/v3r3x8ssvo6GhAZ3pwRwzZkyLP1tYWCAsLAzHjh1DQUEBPvzwQ6MNAIZhsGfP\nHri5ucHe3h4SicTkAgB4sJMYLRrXfnQnQHQqPj4eTk5OnR6IDAoKQn19PXJzczvVsFlYWMDBwQEN\nDQ348MMPMWPGDNbX7deGW7duYeHChcjPz0dycrJBrJ/EBrVajePHjxvFMh2Ggu4EiE6JxWKMGDGi\nU+fw8vKCnZ0dDh48iMbGxk7X5OrqimeeeQZCodDoA4BhGPzwww9wd3fHqFGjcOHCBZMNAAAwMzMD\nl8s1uvEbNtGdANEpiUSCt956S+Pj+/fvDx8fH5w+fRqlpaWdDhQAsLa27hKLipWVlWHBggUoLi5G\nampqq64uQtqD7gSIzpSVlUGpVKJPnz4aHc/hcDB9+nRUV1fj999/11pdlpaWUCgUKC8v19o59Ylh\nGCQkJMDDwwMCgQDnz5+nACAaozsBojM5OTmwtbXV+Nb8hRdewMCBAxEXFweVSqW1ujgcDmxtbZGT\nk2N0u5P9+eefiIiIQFlZGY4cOdLpAXdC6E6A6ExdXZ3Gy0PY2tpi4sSJ+OOPP1BWVqblyh4sJ9HW\n9omGimEYxMbGQiAQ4LnnnkNWVhYFANEKuhMgOqNUKjXajITD4eDVV19FVVWVzvruzc3N0dDQoJNz\na9vNmzcxb948VFZWIi0tDW5ubmyXxCqGYWjgV4soBIjOcLlcqNVqjY7r168fGIbBhx9+2Op9hmEQ\nGBiIwMBAnD59GkeOHOnwNVQqlcE/UcowDLZt24YPP/wQ7733HlasWGHyUx8fDQCVSgVzc3MKhU6i\nECA6w+fzoVAoOnxcU1MTLly40OZ71tbWGDRoEG7cuIGqqiqNl3FWKBQGvYFKSUkJwsPDUVtbi4yM\nDIPfm1hf1Go1vvzyS9y8eRM2NjZ49dVX4eDgwHZZRo1CgOiMm5sbpFJph7+pqVQq/PLLL22+98IL\nL2DQoEG4ePFih5eNeIhhGEilUoPsVlGr1fj222+xZs0aLF++HMuWLUO3bvRrCjyYbbZmzRrExsZi\n+PDhkEql+OSTT/DFF1/g7bffbvHZxsZGqFQq2mC+HWhgmOiMjY0NuFwuampqtHrezt76V1dXg8fj\nGdzMoMLCQvj4+GDnzp04fvw4oqOjKQAeER8fD4lEgpiYGFy+fBkSiQQeHh5Yvnw5JBJJi8+mp6dj\nw4YNLFVqXCgEiE4JBAKtz+7p7Orn5eXlEAgEWqqm89RqNb766it4eXnhlVdewcmTJ+Hs7Mx2WQZn\n165dCAgIwPz589GzZ084OTlBJBLBysoKH3zwQfNAv1qtxnfffYecnByWKzYOFAJEp3x9fVFUVKS1\n8x07dgwbNmzQuCsIePCN29fXV2s1dUZBQQG8vb2xd+9enDp1CsuWLYO5uTnbZRmcxsZG1NTUwMPD\no/lLAIfDweDBg/G///0Phw8fxs6dOwE8mJoskUiaV5wlT0YhQHQqLCwMubm5kMvlbJcC4MHm83l5\neQgNDWW1DpVKhc2bN2PcuHF47bXXcOzYMYwcOZLVmgzZzZs3YW1tjRs3brTqDvT19UV4eDiWL1+O\noqIilJeXo6SkBH5+fixVa1yow5HoVL9+/RAYGGgwm5pkZ2cjKCgI/fr1Y62GvLw8CIVCdOvWDadP\nn8YzzzzDWi3GwsrKCjY2Nrh9+zaAB10+ZmZmzZMO/vvf/+K3337DihUr8OKLL8LKysrotgBlC90J\nEJ2LioqCRCL52z18dU2pVEIikSAqKoqV66tUKnz66aeYMGECQkJCkJGRQQHQTn379sX+/fubnxt5\n+BAih8NBU1MT+vfvj40bN+LEiRNYu3Ytq9uYGhsKAaJzY8eOhY+PDzIyMlitIyMjA1OmTIGnp6fe\nr3316lVMmDABv/76K86ePYvFixdr9DS1KTMzM0PPnj1bvd6tWzeoVCrMnj0bfn5+kMlkCA4OZqFC\n40QbzRO9kMlkcHJygr+/P+zs7PR+/ZKSEqSkpCAvLw99+/bV23Wbmprw2Wef4bPPPsPGjRsRERFB\njb8O1dbWIiUlBa+88opBPwxoSOhvI9ELKysrbN++Hampqaivr9frteVyOVJTUxEbG6vXALh8+TLG\njRuHtLQ0nDt3DgsWLKAA0LHevXtj1qxZFAAdQH8jid4EBARg8ODBiIuL02g5CU0oFAokJSUhNDQU\nAQEBerlmY2MjNm7ciBdffBERERE4cuQIK3c/pkChUGh1mXFTRCFA9Gbz5s24cOEC7t69i+3bt+t8\n2qhcLsfu3bsxbdo0bNq0SafXeignJwdeXl44efIkzp8/j3nz5tHiZjoilUrh6elJ//t2EoUA0Yv9\n+/dj+fLlAB7MkpHJZPj2229RUlKik+uVlJQgISEBwcHBiImJ0XlDwTAMduzYAR8fHyxevBi//vor\nhg4dqtNrmrqMjAw4ODhQF1sn0cAw0bkzZ87A29u7RRcQn8/Hxo0bsXHjRjg4OMDb2xtcLrfT11Iq\nlcjIyEBBQQFiY2M17gISi8XYs2cPVCoVHBwcEB4e/rdrDVVXV6O+vh42NjYaXZN0zLx58+Dq6oql\nS5eyXYpRowglOlVUVISAgIAWAWBubo59+/Zh6dKlyM3NxZAhQ7Bt2zZkZmZq3EUkl8uRmZmJbdu2\nYejQocjNzdUoAJRKJWbNmoU333wTMpkMeXl5WLNmDVasWNH8oNLj9OnThwJAj9LT0/Hiiy+yXYbR\nozsBojMymQzjx49HXl5ei9e///57hIeHt3gtKysLW7ZswcGDB+Ho6Ah7e3tYW1vD0tKyza4chmFQ\nXV2N8vJyFBYWIi8vD0FBQYiKitL4OYCioiLMnTsX9+/fx0cffYQxY8agd+/e2Lx5Mz744ANcv36d\nGnkDUVpaCoFAgDt37lB3UCfRshFEJxoaGvDaa6+1CoBVq1a1CgAA8PT0RGJiIqqqqpCQkACxWIz0\n9HQoFArY2tqCx+PB3NwcKpUKCoUCUqkUPB4PAoEAISEhCA0N7fRSEOXl5bCxscHbb78Nb2/v5vBx\nd3dH9+7d0djY2KnzE+3JyMiAt7c3BYAW0J0A0TqGYfDOO+8gMTGxxeszZ87EDz/80KFf3PLycuTk\n5KCurg4NDQ3o0aMH+Hw+3NzctL4fgFKpRH5+PlxcXFq8vnLlSpw5cwbz5s2Dg4MDRo0aRfPQWTZn\nzhw8++yzWLx4MdulGD0KAaJ1a9aswfr161u8NmHCBBw9etSodnpSKBSYOXMmfvnlF7i6uuL27du4\ne/cu3nrrLWzdutXk9/tl04gRI3Do0CHadlML6F6KaFVCQkKrAHBwcMCBAweMKgCABztZyWQypKen\n4/DhwygrK8Ps2bNx6NAh7Nq1i+3yTNaNGzdw7949jBo1iu1SugQKAaI1aWlprfr7+/Xrh9TUVPTv\n35+lqjS3YMECiMViTJo0CQMGDAAA/Oc//0FdXR3u3LnDcnWm6+F4AD0kph0UAkRreDwennrqqeY/\n9+jRA8nJyUa9XPLDVSsfNjj37t2DUqmk3b9YRFNDtYtCgGjN8OHD0bNnTwwcOBAAsGPHDowfP57l\nqjT31+Fzc1SnAAAcFUlEQVSympoaxMfHw8PDA2+++SZLVZGHdwJEO2iKKNGKe/fuISAgAIsXL0ZE\nRATEYrFRremuUqlafbt/+O2/vLwcRUVFiImJgVgsxscffwxbW1s2yjR5xcXFUCgUcHJyYruULoNC\ngHSaSqXCrFmzIBAIsGrVKnA4HMyePZvtstrl3r17+Oc//4lXXnkFL730UqsgkEgkWLFiBf788088\n9dRTOHr0KNzd3VmqltB4gPZRCJBOYRgGUVFRaGho0MtCbdr0cCDb29sbzz33XJv9/A+7fvh8PmbO\nnMlCleRRNB6gffScAOmUzZs3Iy4uDidPnkSfPn3YLqddamtrsXLlSqSkpGDbtm14+eWXn/j5h5uZ\nE3YxDINhw4bht99+g6OjI9vldBk0MEw09vPPP+Pzzz9HSkqK0QTAkSNH4ObmhqamJly+fPlvAwAA\nBYCBKCoqQlNTE0aOHMl2KV0KdQcRjZw5cwbz58/H4cOHjWLd/JqaGixbtgy//fYbtm3bBl9fX7ZL\nIh2Unp5O4wE6QHcCpMOKi4sxffp0xMXF4dlnn2W7nL/166+/wtXVFd26dcOlS5coAIxURkYGjQfo\nAI0JkA65e/cuxo8fj8WLF2PRokVsl/NEd+/exfvvv4+MjAxs374dPj4+bJdENMQwDAYPHty8mxjR\nHroTIO32cHloPz8/gw+AQ4cOwdXVFb169UJOTg4FgJG7fv06OByOUT99bqhoTIC0C8MwmDdvHvr2\n7YtPP/2U7XIeSyaT4d1330VmZiYSExPpydIu4uHUUBoP0D66EyDtsm7dOuTl5SExMdFgN/I4cOAA\nXF1d0bdvX+Tk5FAAdCG0VITu0JgA+VsJCQlYt24d/vjjj+Z1gQxJZWUlli5diqysLMTFxWHSpEls\nl0S0iGEY2NjYIDMzEyNGjGC7nC7HML/SEYPx+++/Nz9YZYgBsG/fPri6umLQoEG4ePEiBUAXlJ+f\nj+7du2P48OFsl9Il0ZgAeayrV69i1qxZ2Lt3L5ydndkup4U7d+5g8eLFuHjxIn766SejXq2UPBmN\nB+gW3QmQNt26dQv+/v74/PPPDaovlmEY7N27F25ubrCzs0N2djYFQBdH4wG6RWMCpBW5XA5vb28E\nBARg9erVbJfT7Pbt24iMjMS1a9cgEong5eXFdklExxiGgbW1NU6fPg07Ozu2y+mS6E6AtMAwDI4f\nPw4XFxf8+9//ZrscAA9q2rVrF9zc3DBy5EhcuHCBAsBEXLt2DTwejwJAh2hMgLTA4XDg7e0NX19f\ng+iDLS8vx4IFC1BUVISUlBT84x//YLskoke0VITu0Z2ACSktLW3+7yf1Avbs2ZP1ZwEYhsGOHTvg\n7u4ONzc3nDt3jgLABD1cNI7oDo0JmIh169bh1KlTWLVqVfMvlaGuky+VSjF//nyUlpZCJBIZxSJ1\nRPsYhsGAAQNw7tw5DBs2jO1yuizqDjIBubm5WLduHQCgqakJcrkc/v7+4HA4BhUEDMMgPj4e0dHR\nWLRoEfbv3w8ul8t2WUTHysrKkJOTg7q6OiiVSnC5XPD5fPTo0QN8Pp8CQMfoTsBEzJgxA01NTUhP\nT0ffvn2xceNGvPHGG+jRowfbpQF40FU1b9483LlzByKRiPbx7cKqqqoQHx8PsVgMiUQCpVIJW1tb\n8Hg8mJmZQa1WQ6FQ4MaNG+BwOBg/fjx8fX0RFhaGfv36sV1+l0Mh0MWp1WqYmZnh3XffhVqtxtq1\na/Hcc89BJpNh9erVeOedd2BpaYnKykr0799f7/UxDIPt27fjX//6F6KiohAdHY3u3bvrvQ6ie2fP\nnsWWLVuQnJwMJycnjBgxAjY2NujTp0+bd6MMw6CmpgZlZWUoKipCbm4uAgMDERUVhbFjx7LwE3RN\nFAIm4tKlS3j99deRk5MDlUqFqVOn4ty5c1i/fj2KioqQn5+PgwcPonfv3nqr6caNG5g3bx5kMhlE\nIhFcXV31dm2iPzKZDJGRkUhLS4NAIICHhwcsLCw6fB65XI7s7GxIJBL4+Phg69atsLKy0kHFpoVm\nB5mAhwNsDQ0N2LlzJywsLJCZmYlZs2Zh1apViI2Nxfjx4/UWAGq1GjExMfjHP/6ByZMn4/Tp0xQA\nXdTDb/2lpaWIiIjAhAkTNAoAALCwsMCECRMQERGB0tJSODk54dChQ1qu2PRQCJgADoeDgQMHIiQk\nBH/88Ufz65GRkeBwOFCr1bh+/TqysrJ0XktxcTGmTJmC+Ph4HDt2DP/85z/RrRvNT+hqGIbBypUr\nMW/ePPj7+2Pq1KlaG+TncrmYOnUq/P39ER4ejpUrVz5xyjN5MgoBE+Lq6ooDBw5AoVDg6tWreOml\nl7BkyRJ88cUX+PHHH7F48WJUVFTo5NpqtRpff/01PD098fLLLyMzMxOjRo3SybUIuxiGwcKFC/Hj\njz8iLCxMZ0/72tnZITQ0FElJSVi4cCEFgYZoTMCE1NTUwM/PD1FRUVi1ahVGjhyJ+Ph4DBw4EAcP\nHsTNmzexZMkSrV/3+vXrmDt3LhobGxEXFwcnJyetX4MYjhUrVmDfvn2YOXMmeDyezq+nUCiwe/du\nBAcH45NPPtH59boauhMwIX369MHTTz+NmTNnon///vjmm28wYMAAAEBQUJDWA0CtVmPLli147rnn\n8Oqrr+LEiRMUAF1ccnIyduzYgeDgYL0EAADweDwEBwcjISGBxgg0QHcCJqa0tBTfffcdgoKC4Onp\nCUA3Tw7n5+djzpw54HA4iIuLg4ODg1bPTwyPTCaDk5MT/P39WVnwraSkBCkpKcjNzaVZQx1AIWCC\nlEolunfvrpMnhVUqFf73v//ho48+wurVq7F48WLW1yEi+jFz5kyUlpZi6tSprNVw5MgRDB06FLt3\n72atBmNDv51dGMMwUCgUrV7ncrk6CYDc3FxMnDgRhw4dwpkzZ7B06VIKABNx9uxZpKWlsb7Ym7e3\nN44ePaqXmW5dBd0JdGHR0dGYPHkypk6dqtP1gZqamvD555/j008/xfr167FgwQJq/E3M7NmzUVFR\ngQkTJrT7GB6PB2dnZzg4OGDAgAHo3bs3VCoVbt++jezsbGRnZ2tUS2ZmJgYMGIDExESNjjc1FAJd\n1NatW/Hll1/i1KlTOu0fvXLlCoRCIfh8PrZv306bgZugqqoq2NnZYeHChR16EGzMmDHw9/dHXV0d\niouLUVtbCwsLCzg7O4PH4+Hq1avYt29fh+uRy+WIiYlBSUkJrTXUDvSUTheUkpKCDRs2IDMzU2cB\n0NTUhE8++QSbN2/Gf/7zH8ybN89gViMl+hUfHw8nJ6cOPwlcWVmJ3bt3o6CgoMXraWlpmDdvHpyd\nneHk5ITc3NwOndfCwgKOjo5ISEjA+++/36FjTRHds3cxEokEQqEQP//8M0aMGKGTa+Tk5MDLywsZ\nGRk4d+4cIiIiKABMmFgs1ujv2o0bN1oFAADU19fj/Pnz4HA4Gs8ysre3h1gs1uhYU0Mh0IWUlpYi\nICAAMTExeO6557R+/sbGRqxfvx4+Pj6IjIyEWCymtd4JJBIJbGxstHpOlUoF4MGzJpqwtraGRCLR\nZkldFnUHdRG1tbXw9/fHe++9h9dff13r58/OzoZQKGz+5Ro8eLDWr0GMT1lZGZRKJfr06aO1c3I4\nHLi7u4NhGFy/fl2jc1haWkKhUKC8vBzW1tZaq60rojuBLqCxsREzZszAxIkTtd4HqlQqsWbNGkyd\nOhVRUVFISUmhACDNcnJyYGtrq9XuwClTpmDAgAEoKChAUVGRRufgcDiwtbVFTk6O1urqquhOwMgx\nDIPIyEh069YNX375pVZ/Gc+fPw+hUIhhw4YhOztb67f8xPjV1dVpdXmIsWPHYty4caioqMDPP//c\nqXPxeDzU1dVpqbKui0LAyG3atAnnz5/H8ePHtbYkc0NDA9avX4/vv/8eX3zxBWbPnk0Dv6SViooK\nZGdnN/ffd5anpyemTZuGO3fuYMeOHWhoaOjU+czNzTt9DlNAIWDE9uzZg61bt+L06dN46qmntHLO\nrKwsCIVCODg44OLFi9SfSnD37l1cuXIFV65cweXLl5v//XDZcXt7+05fw8vLC76+vrh9+zZ27NiB\n+/fvd/qcKpXKYPbQNmQUAkbq5MmTWLp0KY4ePaqVbhqFQoG1a9dCJBJhy5YtePPNN+nbv4m5d+8e\nrl692qKhv3z5MsrKyp54XH19faeuO2HCBPj4+KC8vBw7d+5sc6kTTSgUCvD5fK2cqyujEDBCBQUF\neOONN5CYmAg3N7dOn+/06dMQCoUYPXo0cnJyMHDgQC1USQzV/fv3kZub26Kxv3LlCkpKSjQ6X2Vl\npcYr0T7//PPw9vaGVCpFYmKi1rpvGIaBVCrVyu9HV0chYGQqKyvh5+eHDRs2dHq1xvv37+Pf//43\nEhMT8dVXX2HGjBlaqpIYAqVSifz8/FaNfWFhocbz7x/1cO2fvLw81NTUwNLSskPHu7u7w9vbG2q1\nGqWlpW0+21JdXY2LFy92uLbq6mrweDzqzmwHCgEjolAoEBQUhBkzZmDevHmdOldmZibmzJkDgUCA\nS5cu4emnn9ZSlUTfmpqaUFhY2Kqxz8/PR1NTU6fP3717dzg6OmL06NFwcXGBi4sLRo8ejREjRsDc\n3BxTp05FWVlZh0PA0tKy+Q7Cy8urzc/cuHFDoxAoLy+HQCDo8HGmiELASKjVaoSGhmLIkCHYuHGj\nxuepr6/HBx98gL179+Lrr7/Ga6+9psUqiT79+9//xqFDh3Dt2jUolcpOn8/MzAwODg7Njf3Dfzs4\nOKB79+6PPc7X1xd79uzp8J7Rx44dw7FjxzpbdpsKCwsREhKik3N3NRQCRuKDDz6AVCrF0aNHNV6m\n+fjx45gzZw68vLxw6dIlWmHRiDEMg8uXL2v0LRkARowY0aqxd3R01GjOf1hYGNauXYsXX3yxw4vI\n6YJcLkdeXh5CQ0PZLsUoUAgYgW3btuGnn37CqVOnNPolvXfvHlatWoX9+/cjJiYGgYGBOqiS6ALD\nMCgvL2/V1XPlypV2DcQOGTKkVWPv7Oys1ca6X79+CAwMRHZ2dof2E9CV7OxsBAUF0ZecdqIQMHCH\nDx/G6tWrceLECfTv37/Dx6enp2Pu3LmYNGkSLl26RHuvGrCKiopWjf3ly5fRvXv35kZ87NixzTO5\nTp482RzogwYNatXYjxo1Sqtr+jxJVFQU/P394enpCS6Xq5drtkWpVEIikSA1NZW1GowNbSpjwC5e\nvIiXXnoJP//8c4e/YdXV1SE6OhqHDh3Ct99+C39/fx1Vadjq6+uRm5uL33//HXfv3sW6deu09mS1\nph738FVjY2OLRnz06NEYPXo0BgwY8NjzXLp0CaNHjzaIb720x7BxohAwUFKpFOPGjcNnn32G4ODg\nDh179OhRhIeHw8fHB59//nmHZ210FUVFRVixYgXOnTuH0tJSAA9WvRw0aJBerl9XV4erV6+2auxr\na2ubG/hHG31ra2ujfkBPJpPByckJ/v7+Gu8D0BklJSVISUlBXl4e+vbtq/frGyvqDjJAdXV1eOWV\nV7Bo0aIOBUBNTQ1WrFiBw4cPY9u2bZg2bZoOqzR8lZWVuHLlCmbMmAE+n48NGzbgxo0bWg+B+/fv\n49q1a20uq+Dk5NTcyPv4+MDFxQVDhgzpknswW1lZYfv27Zg3bx7CwsLQq1cvvV1bLpcjNTUVsbGx\nFAAdRHcCBqapqQmBgYEYPHgwvvvuu3Z/Mzx8+DAiIiIwbdo0fPrpp3rrCzZkarW6ubG9ePEiJk2a\nhC+++ALh4eEanU+pVCIvL69VY//nn3+2ObVy+PDhMDc31+aPZBRWrlyJpKQkzJo1S6srjD6OQqHA\n7t27ERwcjE8++UTn1+tq6E7AgDAMgyVLlkCtVuObb75pVwBUV1fj/fffx++//47Y2Fi89NJLeqjU\nOJiZmTUHAY/Hw8CBA9s1pVKtVqOgoKB57ZyHjX1xcTHs7OyaG/mQkBC4uLjgmWeeeeI8elOzadMm\n1NbWNjfMupw2KpfLkZSUhGnTpmHTpk06u05XRncCnVRWVoacnBzU1dVBqVSCy+WCz+fD3d29w4+s\nf/bZZ9i5cydOnDiB3r17/+3nU1JSsGDBAgQEBGDTpk20WNYTVFRU4O2330ZDQwPS09Of+NmHz1O0\nNY+eVqVsH4ZhEB0djYSEBPj5+elkjKCkpASpqakIDQ3Fpk2bjHo8hU0UAh1UVVWF+Ph4iMViSCQS\nKJVK2NragsfjNX/zVCgUkEql4HK5EAgE8PX1RVhY2BNncOzbtw/vvfce/vjjj7/duevu3bt49913\nceLECWzfvh2TJ0/W9o/Z5dy/fx8rV67EgQMHUFxc/MQZQpouhkZaS05ORnh4OBwcHODt7a2V6aNK\npRIZGRkoKChAbGwsAgICtFCp6aIQaKezZ89iy5YtSE5OhpOTE0aMGAEbGxv06dOnzQaDYRjU1NSg\nrKwMRUVFyM3NRWBgIKKiojB27NgWn/3jjz8QFBSEI0eOwMPD44l1JCcnY+HChXjttdfw0UcfaW0f\nga6OYRh89dVXWLZsGW7evEkLi+mRTCZDZGQk0tLSIBAI4OHhoVEXkVwuR3Z2NiQSCaZMmYJvvvmG\nnnvRAgqBv6GLv8A+Pj7YunUrrKysUFhYiIkTJyI2NhZ+fn6PPb6qqgpLly7FmTNnEBsbixdeeKEz\nP5bRezjz58qVK3jzzTfbNU/+wIEDeO2115CRkYHnn39eD1WSR2VlZWHLli04ePAgHB0dYW9vD2tr\na1haWj72i1R1dTXKy8tRWFiIvLw8BAUFISoqCp6eniz8BF0TDQw/waO3shEREZ26lbWwsMCECRPg\n6emJjIwMODk5YfPmzVi/fj3WrFnzxADYv38/Fi9ejDfffBMXL140iPVZ9KWmpqbNB6sUCkVzX/3L\nL7/crhAYOnQo+Hw+rl27hueffx4qlQpmZmbU9aMnnp6eSExMRFVVFRISEiAWi5Geng6FQtHcpWpu\nbg6VStXcpcrj8SAQCBASEoLQ0FCDeCiuq6E7gTboa1Br//79cHZ2xh9//NFmQ1RRUYElS5bgwoUL\nEIlEBrEui67I5fI2H6y6e/cuRo0a1epJWltb23Y33mq1GhwOB9nZ2QgJCYGrqyvmzJmD/Px8eHp6\nYty4cTr+6ciTlJeXN0+uaGhoQI8ePcDn8+Hm5kbddnpAIfAXDMNg4cKFEIvFCA4O1ukDL49Ob4uJ\niWnRqP34449YsmQJ3nrrLWzYsAE9e/bUWR36pFAokJub26qxv3XrFhwdHVs19sOGDev0g1WXL1/G\nxx9/jJs3b+LkyZPNrz/99NNYv3495s+f39kfixCjRSHwFytWrMC+ffswc+ZMVh50uX37NhYtWoQr\nV64gLi7OaL+lNjY2Ij8/v1Vjf/PmTdjb27dq7O3t7XX2YNX58+cxffp0+Pr6Yty4cRgzZgwcHBz0\n+kQrIYaKQuARycnJrD3ynpCQgLfffhuJiYnN67PrI4Q6S6VSobCwsFVjX1hYiKFDh7Zq7B0cHFhd\nZZIQ0hKFwP8xhMWvdu/ejUOHDhnkU79qtRo3btxo1djn5eVh0KBBrRp7JycnowgxQkwdhcD/oWVw\nH2AYBlKptFVjf+3aNVhaWrZq7J2dnelZBUKMGIUAHjwI5u/v3+lpoJ2lVCqxbds2pKam6nweNMMw\nuHPnTqvG/sqVK+DxeC3Ws3+4QYmpLklNSFdGIQBg9uzZqKio6PAUTGdnZwwbNgyDBg3CwIED0aNH\nD+Tk5ODAgQMa15KZmYkBAwYgMTFR43P8lUwma7OxV6vVzY38o42+JjuYEUKMk8k/LFZVVdW8FENH\nTZo0CQMHDoRSqURtba1WGk8PDw/ExMSgqqqqww/G1NbW4urVq60a+3v37rXownn11VcxevRoDBo0\niB6UIsTEmXwIxMfHw8nJSaOncMViMWpra3H37l0MGzYMoaGhna7HwsICjo6OSEhIwPvvv9/mZ+rr\n63Ht2rVWjX1lZSWcnZ2bG/upU6fCxcUFgwcPpsaeENImkw8BsViMESNGaHTsjRs3tFzNA/b29hCL\nxVi0aBHy8vJaNfZSqRQjR45sbuwXLFiA0aNHY/jw4V1yxypCiO6YfAhIJBK89dZbbJfRgrW1NQ4e\nPAhLS0sMHz68ubF/5513MHr0aDzzzDOsb5ZOCOkaTLolKSsrg1KpNLitGC0tLdGtWzdcvnyZlWcW\nCCGmw6T7DnJycjq0EJm+cDgcDBkyBHl5eWyXQgjp4kw6BOrq6gz2qVYej4e6ujq2yyCEdHEmHQJK\npdJgB1LNzc3R0NDAdhmEkC7OMFtAPeFyuVCr1WyX0SaVSkWbmhNCdM6kQ4DP50OhULBdRpsUCgX4\nfD7bZRBCujiTDgE3NzdIpVIY2soZDxdxc3NzY7sUQkgXZ9JTRG1sbMDlclFTU6PR4miOjo5wdHQE\ngOaVNIcMGYLAwEAAwP379/Hbb791+LzV1dXg8Xi0tR4hROdMOgQAQCAQoKysTKMQGDRoENzd3Zv/\nzDAMLC0tm89VXV2tUQiUl5dDIBB0+DhCCOkokw8BX19f7NmzB6NGjerwsceOHcOxY8e0XlNhYSFC\nQkK0fl5CCPkrkx4TAICwsDDk5uZCLpezXQqAB1tN5uXlaWUxOkII+TsmHwL9+vVDYGAgsrOz2S4F\nAJCdnY2goKAOLyNNCCGaMPkQAICoqChIJBIolUpW61AqlZBIJIiKimK1DkKI6aAQADB27Fj4+Pgg\nIyOD1ToyMjIwZcoUnW8tSQghD9H2kv9HJpPByckJ/v7+rKzcWVJSgpSUFOTl5aFv3756vz4hxDTR\nncD/sbKywvbt25Gamor6+nq9XlsulyM1NRWxsbEUAIQQvaIQeERgYCBCQ0Oxd+9evS0noVAokJSU\nhNDQUAQEBOjlmoQQ8hB1B/0FwzBYuHAhDh8+jODgYI32Hm4vuVyOpKQkTJs2DTExMQa3rwEhpOuj\nO4G/4HA4iImJQXBwMBISElBSUqKT65SUlCAhIQHBwcEUAIQQ1tCdwBMkJycjPDwcDg4O8Pb2BpfL\n7fQ5lUolMjIyUFBQgNjYWOoCIoSwikLgb8hkMkRGRiItLQ0CgQAeHh4adRHJ5XJkZ2dDIpFgypQp\n+Oabb2BlZaWDigkhpP0oBNopKysLW7ZswcGDB+Ho6Ah7e3tYW1vD0tKyza4chmFQXV2N8vJyFBYW\nIi8vD0FBQYiKiqLnAAghBoNCoIOqqqqQkJAAsVgMiUQChUIBW1tb8Hg8mJubQ6VSQaFQQCqVgsfj\nQSAQwNfXF6GhobQUBCHE4FAIdFJ5eTlycnJQV1eHhoYG9OjRA3w+H25ubrQfACHE4FEIEEKICaMp\nooQQYsIoBAghxIRRCBBCiAmjECCEEBNGIUAIISaMQoAQQkwYhQAhhJgwCgFCCDFhFAKEEGLCKAQI\nIcSEUQgQQogJoxAghBATRiFACCEmjEKAEEJMGIUAIYSYMAoBQggxYRQChBBiwigECCHEhFEIEEKI\nCaMQIIQQE0YhQAghJoxCgBBCTBiFACGEmDAKAUIIMWEUAoQQYsIoBAghxIRRCBBCiAmjECCEEBNG\nIUAIISaMQoAQQkwYhQAhhJiw/wcD5qGomsBRSAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10dd54be0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "dg = nx.DiGraph()\n",
    "dg.add_edges_from([(1,2), (2,3), (1,3), (1,4), (3,4)])\n",
    "edge_labels = {(1, 2): 1, (1, 3): 3, (1, 4): 4, (2, 3): 2, (3, 4): 5}\n",
    "\n",
    "pos = nx.spring_layout(dg)\n",
    "nx.draw_networkx_edge_labels(dg,pos,edge_labels=edge_labels, font_size=16)\n",
    "nx.draw_networkx_labels(dg, pos, font_size=20, font_color='w')\n",
    "nx.draw(dg, pos, node_size=1500, node_color=\"gray\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将$A^Ty=0$中的方程列出来：\n",
    "$\n",
    "\\left\\{\n",
    "\\begin{aligned}\n",
    "y_1 + y_3 + y_4 &= 0 \\\\\n",
    "y_1 - y_2 &= 0 \\\\\n",
    "y_2 + y_3 - y_5 &= 0 \\\\\n",
    "y_4 - y_5 &= 0 \\\\\n",
    "\\end{aligned}\n",
    "\\right.\n",
    "$\n",
    "\n",
    "对比看$A^Ty=0$的第一个方程，$-y_1-y_3-y_4=0$，可以看出这个方程是关于节点$1$上的电流的，方程指出节点$1$上的电流和为零，基尔霍夫定律是一个平衡方程、守恒定律，它说明了流入等于流出，电荷不会在节点上累积。\n",
    "\n",
    "对于$A^T$，有上文得出其零空间的维数是$2$，则零空间的基应该有两个向量。\n",
    "\n",
    "* 现在假设$y_1=1$，也就是令$1$安培的电流在边$1$上流动；\n",
    "* 由图看出$y_2$也应该为$1$；\n",
    "* 再令$y_3=-1$，也就是让$1$安培的电流流回节点$1$；\n",
    "* 令$y_4=y_5=0$；\n",
    "\n",
    "得到一个符合KCL的向量$\\begin{bmatrix}1\\\\1\\\\-1\\\\0\\\\0\\end{bmatrix}$，代回方程组发现此向量即为一个解，这个解发生在节点$1,2,3$组成的回路中，该解即为零空间的一个基。\n",
    "\n",
    "根据上一个基的经验，可以利用$1,3,4$组成的节点求另一个基：\n",
    "\n",
    "* 令$y_1=y_2=0$；\n",
    "* 令$y_3=1$；\n",
    "* 由图得$y_5=1$；\n",
    "* 令$y_4=-1$；\n",
    "\n",
    "得到令一个符合KCL的向量$\\begin{bmatrix}0\\\\0\\\\1\\\\-1\\\\1\\end{bmatrix}$，代回方程可知此为另一个解。\n",
    "\n",
    "则$N(A^T)$的一组基为$\\begin{bmatrix}1\\\\1\\\\-1\\\\0\\\\0\\end{bmatrix}\\quad\\begin{bmatrix}0\\\\0\\\\1\\\\-1\\\\1\\end{bmatrix}$。\n",
    "\n",
    "看图，利用节点$1,2,3,4$组成的大回路（即边$1,2,5,4$）：\n",
    "\n",
    "* 令$y_3=0$；\n",
    "* 令$y_1=1$；\n",
    "* 则由图得$y_2=1, y_5=1, y_4=-1$；\n",
    "\n",
    "得到符合KCL的向量$\\begin{bmatrix}1\\\\1\\\\0\\\\-1\\\\1\\end{bmatrix}$，易看出此向量为求得的两个基之和。\n",
    "\n",
    "接下来观察$A$的行空间，即$A^T$的列空间，方便起见我们直接计算\n",
    "$\n",
    "A^T=\n",
    "\\begin{bmatrix}\n",
    "-1 & 0 & -1 & -1 & 0 \\\\\n",
    "1 & -1 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 1 & 0 & -1 \\\\\n",
    "0 & 0 & 0 & 1 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "$\n",
    "的列空间。\n",
    "\n",
    "易从基的第一个向量看出前三列$A^T$的线性相关，则$A^T$的主列为第$1,2,4$列，对应在图中就是边$1,2,4$，可以发现这三条边没有组成回路，则在这里可以说**线性无关等价于没有回路**。由$4$个节点与$3$条边组成的图没有回路，就表明$A^T$的对应列向量线性无关，也就是节点数减一（$rank=nodes-1$）条边线性无关。另外，没有回路的图也叫作树（Tree）。\n",
    "\n",
    "再看左零空间的维数公式：$dim N(A^T)=m-r$，左零空间的维数就是相互无关的回路的数量，于是得到$loops=edges-(nodes-1)$，整理得：\n",
    "\n",
    "$$\n",
    "nodes-edges+loops=1\n",
    "$$\n",
    "\n",
    "此等式对任何图均有效，任何图都有此拓扑性质，这就是著名的欧拉公式（Euler's Formula）。$零维（节点）-一维（边）+二维（回路）=1$便于记忆。\n",
    "\n",
    "总结：\n",
    "\n",
    "* 将电势记为$e$，则在引入电势的第一步中，有$e=Ax$；\n",
    "* 电势差导致电流产生，$y=Ce$；\n",
    "* 电流满足基尔霍夫定律方程，$A^Ty=0$；\n",
    "\n",
    "这些是在无电源情况下的方程。\n",
    "\n",
    "电源可以通过：在边上加电池（电压源），或在节点上加外部电流 两种方式接入。\n",
    "\n",
    "如果在边上加电池，会体现在$e=Ax$中；如果在节点上加电流，会体现在$A^Ty=f$中，$f$向量就是外部电流。\n",
    "\n",
    "将以上三个等式连起来得到$A^TCAx=f$。另外，最后一个方程是一个平衡方程，还需要注意的是，方程仅描述平衡状态，方程并不考虑时间。最后，$A^TA$是一个对称矩阵。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
